package datastructures;

// Random class
//
// CONSTRUCTION: with (a) no initializer or (b) an integer
//     that specifies the initial state of the generator
//
// ******************PUBLIC OPERATIONS*********************
//     Return a random number according to some distribution:
// int randomInt( )                     --> Uniform, 1 to 2^31-1
// int random0_1( )                     --> Uniform, 0 to 1
// int randomInt( int low, int high )   --> Uniform low..high
// long randomLong( long low, long high ) --> Uniform low..high
// void permute( Object [ ] a )         --> Randomly permutate

/**
 * Random number class, using a 31-bit
 * linear congruential generator.
 * Note that java.util contains a class Random,
 * so watch out for name conflicts.
 * @author Mark Allen Weiss
 */
public class Random
{
	private static final int A = 48271;
	private static final int M = 2147483647;
	private static final int Q = M / A;
	private static final int R = M % A;

	/**
	 * Construct this Random object with
	 * initial state obtained from system clock.
	 */
	public Random( )
	{
		this( (int) ( System.currentTimeMillis( ) % Integer.MAX_VALUE ) );
	}

	/**
	 * Construct this Random object with
	 * specified initial state.
	 * @param initialValue the initial state.
	 */
	public Random( int initialValue )
	{
		if( initialValue < 0 )
			initialValue += M;

		state = initialValue;
		if( state == 0 )
			state = 1;
	}

	/**
	 * Return a pseudorandom int, and change the
	 * internal state.
	 * @return the pseudorandom int.
	 */
	public int randomInt( )
	{
		int tmpState = A * ( state % Q ) - R * ( state / Q );
		if( tmpState >= 0 )
			state = tmpState;
		else
			state = tmpState + M;

		return state;
	}

	/**
	 * Return a pseudorandom int, and change the
	 * internal state. DOES NOT WORK.
	 * @return the pseudorandom int.
	 */
	public int randomIntWRONG( )
	{
		return state = ( A * state ) % M;
	}

	/**
	 * Return a pseudorandom double in the open range 0..1
	 * and change the internal state.
	 * @return the pseudorandom double.
	 */
	public double random0_1( )
	{
		return (double) randomInt( ) / M;
	}

	/**
	 * Return an int in the closed range [low,high], and
	 * change the internal state.
	 * @param low the minimum value returned.
	 * @param high the maximum value returned.
	 * @return the pseudorandom int.
	 */
	public int randomInt( int low, int high )
	{
		double partitionSize = (double) M / ( high - low + 1 );

		return (int) ( randomInt( ) / partitionSize ) + low;
	}

	/**
	 * Return an long in the closed range [low,high], and
	 * change the internal state.
	 * @param low the minimum value returned.
	 * @param high the maximum value returned.
	 * @return the pseudorandom long.
	 */
	public long randomLong( long low, long high )
	{
		long longVal =  ( (long) randomInt( ) << 31 ) + randomInt( );
		long longM =  ( (long) M << 31 ) + M;

		double partitionSize = (double) longM / ( high - low + 1 );
		return (long) ( longVal / partitionSize ) + low;
	}
	/**
	 * Randomly rearrange an array.
	 * The random numbers used depend on the time and day.
	 * @param a the array.
	 */
	public static final void permute( Object [ ] a )
	{
		Random r = new Random( );

		for( int j = 1; j < a.length; j++ )
			Sort.swapReferences( a, j, r.randomInt( 0, j ) );
	}

	private int state;

	// Test program
	public static void main( String [ ] args )
	{
		Random r = new Random( 1 );

		for( int i = 0; i < 20; i++ )
			System.out.println( r.randomInt( ) );
	}
}
